|
Hamming graphs are a special class of graphs named after Richard Hamming and used in several branches of mathematics and computer science. Let ''S'' be a set of ''q'' elements and ''d'' a positive integer. The Hamming graph ''H''(''d'',''q'') has vertex set ''Sd'', the set of ordered ''d''-tuples of elements of ''S'', or sequences of length ''d'' from ''S''. Two vertices are adjacent if they differ in precisely one coordinate; that is, if their Hamming distance is one. The Hamming graph ''H''(''d'',''q'') is, equivalently, the Cartesian product of ''d'' complete graphs ''K''''q''.〔.〕 In some cases, Hamming graphs may be considered more generally as the Cartesian products of complete graphs that may be of varying sizes.〔.〕 Unlike the Hamming graphs ''H''(''d'',''q''), the graphs in this more general class are not necessarily distance-regular, but they continue to be regular and vertex-transitive. ==Special Cases== *''H''(2,3), which is the generalized quadrangle ''G'' ''Q'' (2,1)〔. See in particular note (e) on p. 300.〕 *''H''(1,''q''), which is the complete graph ''K''''q''〔.〕 *''H''(2,''q''), which is the lattice graph ''L''''q,q'' and also the rook's graph〔.〕 *''H''(''d'',1), which is the singleton graph ''K''1 *''H''(''d'',2), which is the hypercube graph ''Q''''d''〔 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Hamming graph」の詳細全文を読む スポンサード リンク
|